import java.util.Stack;

public class Sort {
    // 插入排序
    public static void insertSort(int[] array){
        // write code  here
        for(int i = 1; i < array.length; i++){
            int tmp = array[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    // 希尔排序
    public static void shellSort(int[] array){
        // write code  here
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell(array, gap);
        }
    }
    private static void shell(int[] array, int gap){
        for(int i = 0; i < array.length; i++){
            int tmp = array[i];
            int j = i - gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j + gap] = array[j];
                }else{
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    // 选择排序
    public static void selectSort(int[] array){
        // write code  here
        for(int i = 0; i < array.length - 1; i++){
            int minIndex = i;
            for(int j = i + 1; j < array.length; j++){
                if(array[minIndex] > array[j]){
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

// 堆排序
    public static void heapSort(int[] array){
        // write code  here
        createHeap(array);
        int index = array.length - 1;
        while(index >= 0){
            swap(array, 0, index);
            shiftDown(array, 0, index);
            index--;
        }
    }
    private static void shiftDown(int[] array, int parent, int len){
        int child = 2 * parent + 1;
        while(child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array, parent, child);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }
    private static void createHeap(int[] array){
        int parent = (array.length - 1 - 1) / 2;
        for(; parent >= 0; parent--){
            shiftDown(array, parent, array.length);
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array){
        // write code  here
        for(int i = 0; i < array.length - 1; i++){
            boolean flag = false;
            for(int j = 0; j < array.length - 1 - i; j++){
                if(array[j] > array[j + 1]){
                    swap(array, j, j + 1);
                    flag = true;
                }
            }
            if(!flag){
                break;
            }
        }
    }

    // 快速
    public static void quickSort(int[] array){
        // write code  here
        int left = 0;
        int right = array.length - 1;
        quick(array, left, right);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right){
            return;
        }
        //后两层就用插入法进行排序
        if(right - left + 1 <= 7){
            //区间插入排序
            insertSortRange(array, left, right);
            return;
        }
        //三数取中法 - 二分查找
        int mid = midOfThree(array, left, right);
        //保证left下标对应的是是中间大的数字
        swap(array, left, mid);

        int pivot = partition(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    private static int partition(int[] array, int left, int right) {
        //挖坑法
        int tmp = array[left];
        while(left < right){
            while(left < right && array[right] >= tmp){
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    private static int partition2(int[] array, int left, int right){
        int tmp = array[left];
        int index = left;
        while(left < right){
            while(left < right && array[right] >= tmp){
                right--;
            }
            while(left < right && array[left] <= tmp){
                left++;
            }
            swap(array, left, right);
        }
        swap(array, index, left);
        return left;
    }

    //快排优化
    //三数取中法
    private static int midOfThree(int[] array, int left, int right){
        int mid = (left + right) / 2;
        if (array[left] > array[right]) {
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] > array[right]){
                return right;
            }else if(array[mid] < array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }

    private static void insertSortRange(int[] array, int left, int right){
        for(int i = left + 1; i <= right; i++){
            int tmp = array[i];
            int j = i - 1;
            for(; j >= left; j--){
                if(array[j] > tmp){
                    array[j + 1] = array[j];
                }else{
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    //快排 - 非递归方法
    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        //第一次需要找基准
        int pivot = partition(array, left, right);
        if(pivot - 1 > left){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot + 1 < right){
            stack.push(pivot + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array, left, right);
            if(pivot - 1 > left){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot + 1 < right){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    private static void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //归并排序 - 递归的方法
    public static void mergeSort(int[] array){
        int left = 0;
        int right = array.length - 1;
        mergeSortFunc(array, left, right);
    }

    private static void mergeSortFunc(int[] array, int left, int right){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        //先分解左边
        mergeSortFunc(array, left, mid);
        //再分解右边
        mergeSortFunc(array, mid + 1, right);
        //再合并
        merge(array, left, right, mid);
    }
    private static void merge(int[] array, int left, int right, int mid){
        int s1 = left;
        int s2 = mid + 1;
        int[] tmpArr = new int[right - left + 1];
        int k = 0;
        while(s1 <= mid && s2 <= right ){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        while(s1 <= mid){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= right){
            tmpArr[k++] = array[s2++];
        }
        for(int i = 0; i < k; i++){
            array[i + left] = tmpArr[i];
        }
    }

    //归并排序 - 非递归方法
    public static void mergeSortNor(int[] array){
        int gap = 1;
        while(gap < array.length){
            for(int i = 0; i < array.length; i+=(2*gap)){
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= array.length){
                    mid = array.length - 1;
                }
                if(right >= array.length){
                    right = array.length - 1;
                }
                merge(array, left, right, mid);
            }
            gap *= 2;
        }

    }
}
